/*
 *    array_sort.hpp (WordTrending)
 *    Asif Shahidullah
 *
 *    Defines the template pattern for the merge sort algorithm. The
 *    code is contained in a class incase of future expansions to the
 *    behaviour.
 *
 *    This implementation utilizes the bottom-up technique, which is an
 *    iterative variation of merge sort. See README: Development Notes 9.
 *
 */

namespace ece { namespace sort {
   template <typename E>
   class array_sort {
   public:
      void mergesort (E data[], const unsigned int& size);
   private:
      unsigned int min (const unsigned int& a, const unsigned int& b) 
         { return (a < b)? a:b; }
      void merge (E data[], E temp_array[], const unsigned int& index, 
         const unsigned int& block_sz, const unsigned int& size);
   };
}}

template <typename E>
/* Applies the mergesort algorithm to the passed array of values.
   The of the array has to be explicity stated as this gives two
   advantages: the size does not need to be calculated, and, only
   part of an array can be sorted.

   The abstract type (E) needs to be comparable and assignable, i.e., 
   overload the binary comparison operator '<='. The object needs to
   be assignable too, i.e., overload the assignment operator '='. */
void ece::sort::array_sort<E>::mergesort(E data[], const unsigned int& size)
{
   E* temp_array = new E[size];

   unsigned int block_sz = 1, index = 0, j;

   while (block_sz < size) {
      while (index < size) {
         merge (data, temp_array, index, min(index + block_sz, size), 
            min(index + 2 * block_sz, size));
         index += (2 * block_sz);
      }

      // Repopulate data with the sorted blocks
      for (j = 0; j < size; j++)
         data[j] = temp_array[j];

      index = 0;
      block_sz *= 2;
   }

   delete [] temp_array;
}

template <typename E>
/* Performs the merge operation on the specified portion
   of the data array. The sorted portion is placed in the
   sorted array. */
void ece::sort::array_sort<E>::merge(E data[], E temp_array[],
                                     const unsigned int& index,
                                     const unsigned int& right,
                                     const unsigned int& end)
{
   unsigned int c1 = index, c2 = right, i;
   for (i = index; i < end; i++) {
      // Switch from ascending descending order ('<=' to '>=')
      //if (c1 < right && (c2 >= end || data[c1] <= data[c2]))
      if (c1 < right && (c2 >= end || data[c1] >= data[c2]))
         temp_array[i] = data[c1++];
      else
         temp_array[i] = data[c2++];
   }
}
